package basic.basic_class08;

/**
 * 汉诺塔问题
 * 面试题 08.06. 汉诺塔问题
 *
 * 打印n层汉诺塔从最左边移动到最右边的全部过程
 */
public class Code_02_Hanoi {

    // 打印汉诺塔移动的全部过程
    public static void printHanoi(int n) {
        printProcess(3,"左","右","中");
    }

    /**
     * 转移过程(将n个塔从form转移到to)
     * @param n
     * @param from
     * @param to
     * @param help
     */
    public static void printProcess(int n, String from, String to, String help) {
        //终止条件
        if(n == 1) {
            System.out.println("move " + n + " from " + from + " to " + to );
            return;  // 一定要加上这个return,否则递归没有终止条件
        }
        //先将n-1个塔移动到help的位置
        printProcess(n-1,from,help,to);
        //将最后一个n转移到to位置
        System.out.println("move " + n + " from " + from + " to " + to );
        //再将n-1个塔从help位置移动到to的位置
        printProcess(n-1,help,to,from);
    }

    public static void main(String[] args) {
        int n = 3;
        printHanoi(n);
    }
}
